Die Sicherheit des RSA-Verfahrens hängt von der Schwierigkeit ab, natürliche Zahlen in ihre Primfaktoren zu zerlegen. Ob das Faktorisierungsproblem für natürliche Zahlen einfach zu lösen ist, ist nicht bekannt. Die Probedivision ist dabei sehr ineffizient. In den letzten Jahren sind allerdings immer bessere Verfahren entdeckt worden. Für den Fall, dass ein effizientes Verfahren entdeckt wird müssen kryptographische Algorithmen so aufgebaut sein, dass das grundlegende Verfahren leicht geändert werden kann.

\subsection{Probedivision [Buchmann: 10.1]}
Um die kleinen Primfaktoren von $n$ zu finden, berechnet man die Liste aller Primzahlen unter einer festen Schranke $B$ (z.B. über das Sieb des Erasthostenes). Anschließend wird für jede Zahl $p$ in der Liste der maximale Exponent $e(p)$ ermittelt, für den $p^{e(p)}$ die Zahl $n$ teilt.

\paragraph{Beispiel:}
Sei $n = 3^{21} + 1 = 10460353204$ und die Schranke $B = 50$\\
Daraus ergeben sich die Primzahlen: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$\\
Sowie die Faktoren mit maximalem Exponenten:\\
$e(2) = 2 \Rightarrow 2^2$\\
$e(7) = 2 \Rightarrow 7^2$\\
$e(43) = 1 \Rightarrow 43^1$\\
$e(3)=e(5)=e(11)=e(13)=e(17)=e(19)=e(23)=e(29)=e(31)=e(37)=e(41)=e(47)=0$\\
Daraus folgt: $m = \frac{10460353204}{2^2 * 7^2 * 43^1} = 1241143$\\
Nach dem kleinen Satz von Fermat ist $m$ zusammengesetzt, da:\\
$2^{m-1} \equiv 793958 \not\equiv 1 \mod m$\\
Dabei sind alle Faktoren größer $B$.

\subsection{Das quadratische Sieb [Buchmann: 10.3]}
Eine zusammengesetzte Zahl $n$ soll faktorisiert werden. Es wird versucht einen echten Teiler von $n$ zu finden. Ist $n$ Produkt zweier Primzahlen, so ist die Primfaktorzerlegung gefunden. Andernfalls müssen die gefundenen Faktoren ihrerseits faktorisiert werden.\\
Im quadratischen Sieb werden dabei zwei Zahlen $x$ und $y$ bestimmt, für die gilt:\\
$x^2 \equiv y^2 \mod n$ und $x \not\equiv \pm y \mod n$\\
Daraus ergibt sich $n$ ist Teiler von $x^2 - y^2 = (x-y)(x+y)$, aber nicht von $x-y$ und $x+y$.\\
Daraus folgt: $g=gcd(x-y, n)$ ist echter Teiler von $n$.\\
($1<gcd(x+y,n)<n$ ist ebenfalls ein echter Teiler.)

\paragraph{Beispiel:}
Sei $n=7429$, $x=227$, $y=210$. Dann ist $x^2-y^2=n$, $x-y=17$, $x+y=437$.\\
Daher ist $gcd(x-y, n)=17$ und somit ein echter Teiler von n.\\

Die Faktoren $x$ und $y$ werden wie folgt bestimmt.\\
$m = \lfloor \sqrt{n} \rfloor$\\
$f(X) = (X+m)^2-n$
\newpage

\paragraph{Beispiel:}
Sei $n=7429$, dann ist $m=86$ und $f(X)=(X+86)^2-7429$.  Für dieses Beispiel wurde $X$ so gewählt das nur kleine Primfaktoren entstehen. Es gilt\\
$f(-3)=83^2-7429=-540=-1*2*2*3*3*3*5=-1*2^2*3^3*5$\\
$f(1)=87^2-7429=140=2*2*5*7=2^2*5*7$\\
$f(2)=88^2-7429=315=3*3*5*7=3^2*5*7$\\
Daraus folgt\\
$83^2 \equiv -1*2^2*3^3*5 \mod 7429$\\
$87^2 \equiv 2^2*5*7 \mod 7429$\\
$88^2 \equiv 3^2*5*7 \mod 7429$\\
Multipliziert man die letzten beiden Kongruenzen, so erhält man\\
$(87*88)^2 \equiv (2*3*5*7)^2 \equiv 6955 \mod n$\\
Daraus lasen sich $x$ und $y$ wie folgt ermitteln.\\
$x=87*88 \mod n=227$ und $y=2*3*5*7 \mod n = 210$\\

Um ein kleines $X$ zu ermitteln wird ausgenutzt, dass $(X+m)^2 \equiv f(X) \mod n$ ist. Dabei werden Kongruenzen ausgewählt, bei denen auf beiden Seiten ein Quadrat steht. Auf der linken Seite ist dies automatisch der Fall. Auf der rechten Seite, wenn die Exponenten aller Primfaktoren und von $-1$ gerade ist.

\subsubsection{Auswahl einer geeigneten Kongruenz [Buchmann: 10.3.3]}
Während die Auswahl bei kleinen Kongruenzen direkt ersichtlich ist, wird dies bei großen Zahlen schnell sehr aufwändig. Dieses Problem löst man mit linearer Algebra, wie im nächsten Beispiel illustriert.

\paragraph{Beispiel:}
Man sucht Zahlen $\lambda_i \in \{0,1\}, 1 \le i \le 3$  für die folgendes ein Quadrat ist.\\
$(-1*2^2*3^3*5)^{\lambda_1} * (2^2*5*7)^{\lambda_2} * (3^2*5*7)^{\lambda_3} = $\\
$(-1)^{\lambda_1} * 2^{2\lambda_1+2\lambda_2} * 3^{3\lambda_1+2\lambda_3} * 5^{\lambda_1+\lambda_2+\lambda_3} * 7^{\lambda_2+\lambda_3}$\\

Man erhält das folgende Kongruenzsystem.\\
$\lambda_1 \equiv 0 \mod 2$\\
$2\lambda_1 + 2\lambda_2 \equiv 0 \mod 2$\\
$3\lambda_1 + 2\lambda_3 \equiv 0 \mod 2$\\
$\lambda_1 + \lambda_2 + \lambda_3 \equiv 0 \mod 2$\\
$\lambda_2 + \lambda_3 \equiv 0 \mod 2$\\

Den Koeffizienten der Unbekannten $\lambda_i$ kann man $\mod 2$ reduzieren und erhält dann ein vereinfachtes System. Aus dem sich die Lösung ermitteln lässt.\\
$\lambda_1 \equiv 0 \mod 2 \Rightarrow \lambda_1 = 0$\\
$\lambda_2 + \lambda_3 \equiv 0 \mod 2 \Rightarrow \lambda_2 = \lambda_3 = 0$\\
$\lambda_1 + \lambda_2 + \lambda_3 \equiv 0 \mod 2$\\

Im folgenden wird gezeigt, wie das quadratische Sieb geeignete Kongruenzen im allgemeinen findet. Dazu wählt man eine natürliche Zahl $B$. Gesucht werden dann kleine ganze Zahlen $s$, für die $f(s)$ nur Primfaktoren aus der Faktorbasis $F(B)$ hat.\\
$F(B)=\{p \in \mathbb P : p \le B\} \cup \{-1\}$\\

Ein solches $f(s)$ wird im Allgemeinen als $B$-glatt bezeichnet.  Es werden so viele $s$ ermittelt wie $F(B)$ Elemente hat. Anschließend wird das Gleichungssystem aufgestellt und gelöst. Da es sich um ein Gleichungssystem über dem Körper $\Z/2\Z$ handelt, kann der Gauß-Algorithmus verwendet werden.
\newpage

\subsubsection{Das Sieb [Buchmann: 10.3.4]}
Die einfachste Variante $s$ zu finden für die $f(s)$ $B$-glatt ist  für beliebige $s$ das entsprechende $f(s)$ zu ermitteln und über Probedivision prüfen ob er $B$-glatt ist. Dies ist allerdings sehr aufwendig. Statt dessen wird ein Siebverfahren verwendet.\\
Dafür wird zuerst ein Siebintervall festgelegt.\\
$S=\{-C,-C+1,...,0,1,...,C\}$\\

Gesucht werden alle $s \in S$, für die $f(s)$ B-Glatt ist. Zu Beginn werden alle $f(s)$ berechnet. Alle berechneten Werte werden dann für alle $p$ der Faktorbasis durch die höchstmögliche $p$-Potenz dividiert. Bei B-Glatt Werten bleibt eine $1$ oder $-1$ stehen.\\
Um herauszufinden, welche $f(s)$ durch eine Primzahl $p$ der Faktorbasis teilbar sind, werden zuerst die Zahlen $s \in \{0,1,...,p-1\}$ bestimmt für die gilt: $p | f(s)$.\\
Da $\deg f(X) = 2$ ist, können maximal zwei Nullstellen existieren, also maximal 2 passende $s$ gefunden werden. Für kleine Primzahlen kann dies durch probieren erreicht werden. Bei großen Zahlen geht man anders vor.\\
Wenn eine Nullstelle $s_1$ gefunden ist, kann die andere über $s_2 = -2m - s_1 \mod p$ berechnet werden. Wenn nur eine Nullstelle von $f(s) \mod p$ vorhanden ist, dann ist $s_1 = s_2$\\
\paragraph{Beweis:}
$f(s_1) \equiv 0 \mod p \Rightarrow \exists a \in \mathds{Z}$ für das gilt: $f(s_1) + a \cdot p = 0$\\
$(s + m)^2 - n + ap = 0$\\
$s_{1,2}=\frac{-2m \pm\sqrt{4m^2-4(m^2-n+ap)}}2$\\
$s_{1,2}=-m \pm\sqrt{n-ap}$\\
$s_1 = -m \pm\sqrt{n-ap}$ ist erste Lösung durch Probieren.\\
$\Rightarrow a = -\frac{(s_1 + m)^2 - n}p$\\
$s_2=-m - \sqrt{n + p \cdot \frac{(s_1 + m)^2 - n}p}$\\
$s_2=-m - \sqrt{(s_1 + m)^2}$\\
$s_2=-m -s_1 - m = -2m - s_1$\\
$(s_2 + m)^2 - n + ap = (-2m - s_1 + m)^2 - n + ap = (-m - s_1)^2 - n + ap = (-1(s_1 + m))^2 - n + ap = (s_1 + m)^2 - n + ap = 0$\\

Zusätzliche Hinweise:\\
Für $p = 2$ hat $f(X)$ immer genau eine Nullstelle.\\
\begin{tabular}{|l|l|l||l|l|l|l|} \hline
$x$ & $m$      & $n$      & $(x + m)$ & $(x + m)^2$ & $(x + m)^2 - n$ & $(x + m)^2 - n \mod 2$ \\\hline
0   & gerade   & gerade   & gerade    & gerade      & gerade          & 0						\\\hline
1   & gerade   & gerade   & ungerade  & ungerade    & ungerade        & 1						\\\hline\hline
0   & gerade   & ungerade & gerade    & gerade      & ungerade        & 1						\\\hline
1   & gerade   & ungerade & ungerade  & ungerade    & gerade          & 0						\\\hline\hline
0   & ungerade & gerade   & ungerade  & ungerade    & ungerade        & 1						\\\hline
1   & ungerade & gerade   & gerade    & gerade      & gerade          & 0						\\\hline\hline
0   & ungerade & ungerade & ungerade  & ungerade    & gerade          & 0						\\\hline
1   & ungerade & ungerade & gerade    & gerade      & ungerade        & 1						\\\hline
\end{tabular}


$f(X)$ hat genau eine Nullstelle $\mod p$ für $x \in \{0,..,p-1\}$ und $p > 2 \Leftrightarrow p | n$\\
\newpage
Ausgehend von der Nullstelle wandert man in Schritten der Länge $p$ nach rechts und links. Auf diese Weise findet man alle $s$-Werte für die $f(s)$ durch $p$ teilbar ist.\\
Der Vorgang wird Sieb mit $p$ genannt.
Wenn ein $s$ gefunden wurde, für das $f(s) \equiv 0 \mod p$ gilt, gilt auch:

$f(s + kp) = (s + kp + m)^2 - n =$\\
$s^2 + k^2p^2 + m^2 + 2skp + 2mkp + 2sm - n =$\\
$s^2 + 2sm + m^2 - n + p(2sk + 2mk + k^2p) =$\\
$(s + m)^2 - n + p(2sk + 2mk + k^2p)$\\
$(s + m)^2 - n = f(s) \equiv 0 \mod p$ und $p(2sk + 2mk + k^2p) \equiv 0 \mod p$\\
$\Rightarrow f(s + kp) \equiv 0 \mod p$ für $k \in \mathds{Z}$

Alternativ:\\
$f(s + kp) = ((s + kp) + m)^2 - n \equiv (s + m)^2 - n = f(s) \equiv 0 \mod p$

\paragraph{Beispiel:}
Sei $n=7429$, $m=86$ und $f(X)=(X+86)^2-7429$.\\
Als Faktorbasis wird die Menge $\{2,3,5,7\} \cup \{-1\}$\\
und als Siebintervall die Menge $\{-3,-2,-1,0,1,2,3\}$ gewählt.

\begin{tabular}{|l|l|l|l|l|l|l|l||l|} \hline
$s$         & $-3$   & $-2$   & $-1$   & $0$   & $1$   & $2$   & $3$   & Nullstelle bei\\
$(s+m)^2-n$ & $-540$ & $-373$ & $-204$ & $-33$ & $140$ & $315$ & $492$ & \\ \hline
Sieb mit 2  & $-135$ &        & $-51$  &       & $35$  &       & $123$ & $1$\\ \hline
Sieb mit 3  & $-5$   &        & $-17$  & $-11$ &       & $35$  & $41$  & $0; 2$\\ \hline
Sieb mit 5  &\cellcolor{lightgray}  $-1$   &        &        &       & $7$   & $7$   &       & $1; 2$\\ \hline
Sieb mit 7  &        &        &        &       &\cellcolor{lightgray} $1$   &\cellcolor{lightgray} $1$   &       &$ 1; 2$\\ \hline
$B$ glatt     &\checkmark $(B = 5)$&        &        &       &\checkmark $(B = 7)$&\checkmark $(B = 7)$&       &\\ \hline
\end{tabular}

\subsubsection{Analyse des Quadratischen Siebs [Buchmann: 10.4]}
Das quadratische Sieb ist wesentlich effizienter als die Probedivision. Die Analyse des Verfahrens wird grob Skizziert.\\
Angenommen $n$, $u$, $v$ sind reelle Zahlen und $n$ sei größer als die Eulersche Konstante $e$. Man definiert:\\
$L_n[u,v] = e^{v (\log n)^u (\log \log n)^{1-u}}$\\

Speziell für $u = 0$ bzw. $u = 1$ erhält man:\\
$L_n[0,v] = e^{v (\log n)^0 (\log \log n)^1}=(\log n)^v$\\
$L_n[1,v] = e^{v (\log n)^1 (\log \log n)^0}=e^{v \log n}$\\

Ein Algorithmus welcher $n$ faktorisieren soll erhält diesen Wert als Eingabe. Die binäre Länge von $n$ ist $\lfloor \log_2 n \rfloor + 1 = O(\log n)$. Wenn der Algorithmus die Laufzeit $L_n[0,v]$ hat ist seine Laufzeit polynomiell, wobei $v$ der Grad des Polynoms ist. Ein entsprechender Algorithmus gilt als effizient, wobei die Laufzeit vom Grad des Polynoms abhängig ist.\\
Hat der Algorithmus die Laufzeit $L_n[1,v]$, so ist sie exponentiell und damit ineffizient.\\
Ein Algorithmus mit der Laufzeit $L_n[u,v]$ und $0 < u < 1$ ist subexponentiell. Und damit besser als exponentiell.\\
Die Laufzeit der Probedivision zur Faktorisierung ist exponentiell. Die Laufzeit des quadratischen Siebs ist noch nicht völlig analysiert. Es wurde aber eine plausible Annahme getroffen. Dabei ist die Laufzeit $L_n[1/2,1+o(1)]$. $o(1)$ konvergiert gegen 0 wobei $n$ gegen Unendlich geht. Die Laufzeit liegt somit genau mittig zwischen polynomiell und exponentiell.
\newpage

\subsection{Effizienz anderer Faktorisierungsverfahren [Buchmann: 10.5]}
Der effizienteste Faktorisierungsalgorithmus, dessen Laufzeit bewiesen werden kann, benutzt quadratische Formen. Seine Laufzeit liegt auf gleich auf mit der des quadratischen Siebs. Die Elliptische-Kurven-Methode ist ein weiteres Verfahren, das abhängig von $n$ schneller oder langsamer als das quadratische Sieb ist.\\
1988 hatte der schnellste Faktorisierungsalgorithmus eine Laufzeit von $L_n[1/2,1]$. In den letzten Jahren wurden diesbezüglich allerdings deutliche Fortschritte erreicht. Das Zahlenkörpersieb beispielsweise hat eine Laufzeit von $L_n[1/3,(64/9)^{1/3}]$. Darüber hinaus wurde beweisen, dass Quantencomputer Faktorisierungen mit polynomieller Effizienz berechnen können.\\
Im Folgenden sind drei aktuelle Faktorisierungsrekorde aufgelistet:
\begin{itemize}
\item General-purpose Algorithm (2009): 232 Stellen in ca. 2.000 Prozessorjahren
\item Elliptic Curve Method (2012): 79 Stellen
\item Special Number Field Sieve (2012): 320 Stellen
\end{itemize}

